#include <stdio.h>

/* 1.循环的解法，自底向上累加
   2.递归的解法：此方法时间复杂度过高，导致时间过长
   3.递归的解法，用HashMap存储中间计算结果
*/

int climbStairs(int n)
{
    if (n == 1)
    return 1;
    if (n == 2)
    return 2;
    
    int result = 0;
    int pre = 2;
    int prePre = 1;
    for (int idx = 3; idx <= n; idx++)
    {
        result = pre + prePre;
        prePre = pre;
        pre = result;

    }
    return result;
}

int main()
{
    int n = 0;
    printf("enter a number:\n");
    scanf("%d", &n);
    int ret = climbStairs(n);
    printf("ret = %d\n", ret);

    return 0;
}